package dp.subsequence;

/**
 * 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
 *
 * 示例 1:
 * 输入: "bbbab"
 * 输出: 4
 * 一个可能的最长回文子序列为 "bbbb"。
 *
 * 示例 2:
 * 输入:"cbbd"
 * 输出: 2
 * 一个可能的最长回文子序列为 "bb"。
 */
public class leetCode516_longestPalindromeSubseq {
    /**
     * dp[i][j] 字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
     * @param s
     * @return
     */
    public int longestPalindromeSubseq(String s) {

        int m = s.length();
        int[][] dp = new int[m][m];
        for (int i = 0; i < m; i++) dp[i][i] = 1;


        for (int i = m - 1; i >= 0; i--) {
            for (int j = i + 1; j <= m - 1; j++) {
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);
                }
            }
        }

        return dp[0][m-1];
    }

    /**
     * dp[i][j] 表示【i，j】区间的最长公共子序列的长度
     * @param s
     * @return
     */
    public int longestPalindromeSubseq2(String s) {
        int m = s.length();

        int[][] dp = new int[m][m];
        for (int i = 0; i < m; i++) {
            dp[i][i] = 1;
        }

        for (int i = m-1; i >= 0; i--) {
            for (int j = i + 1; j <= m - 1; j++) {
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[0][m-1];




    }

    public static void main(String[] args) {
        String a = "aaaba";
        leetCode516_longestPalindromeSubseq aa = new leetCode516_longestPalindromeSubseq();
        int i = aa.longestPalindromeSubseq3(a);
        System.out.println(i);
    }

    // dp[i][j]：字符串s在[i,j]范围内最长的回文子序列的长度为dp[i][j]。
    public int longestPalindromeSubseq3(String s) {
        int n = s.length();
        if(n < 2){
            return 1;
        }
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int i = n - 1; i >= 0 ; i--) {
            for (int j = i + 1; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];


    }

}
